import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class project {
    Map<String,Integer> map=new HashMap<>();
    List<TreeNode> list=new ArrayList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        dfs(root);
        return list;
    }
    public  String dfs(TreeNode root){
        if(root==null){
            return "#";
        }
        String str=root.val+","+dfs(root.left)+","+dfs(root.right);
        map.put(str,map.getOrDefault(str,0)+1);
        if(map.get(str)==2){
            list.add(root);
        }
        return str;
    }

















    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String ,List<String>> map=new HashMap<>();
        List<List<String>> list=new ArrayList<>();
        for(String str:strs){
            char[] sort=str.toCharArray();
            Arrays.sort(sort);
            String key=new String(sort);
            List<String> tmp=map.getOrDefault(key,new ArrayList<>());
            tmp.add(str);
            map.put(key,tmp);
        }
        for(Map.Entry<String,List<String>> entry:map.entrySet()){
            list.add(entry.getValue());
        }
        return list;
    }


















    public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
        List<List<Integer>> list=new ArrayList<>();
        Set<Integer> set1=new HashSet<>();
        Set<Integer> set2=new HashSet<>();
        for(int num:nums2){
            set2.add(num);
        }
        List<Integer> value=new ArrayList<>();
        for(int num:nums1){
            set1.add(num);
            if(!set2.contains(num)&&!value.contains(num)){
                value.add(num);
            }
        }
        list.add(value);
        value=new ArrayList<>();
        for(int num:nums2){
            if(!set1.contains(num)&&!value.contains(num)){
                value.add(num);
            }
        }
        list.add(value);
        return list;
    }

















    public int deleteAndEarn(int[] nums) {
        Arrays.sort(nums);
        int[] dp=new int[nums[nums.length-1]+1];
        for(int num:nums){
            dp[num]+=num;
        }
        for(int i=2;i<dp.length;i++){
            dp[i]=Math.max(dp[i]+dp[i-2],dp[i-1]);
        }
        return dp[dp.length-1];
    }
















    public static int maxConsecutiveAnswers(String answerKey, int k) {
        int max=0;
        int countF=0;
        int countT=0;
        int left=0;
        int right=0;
        int len=answerKey.length();
        while (right<len){
            char ch=answerKey.charAt(right);
            if(ch=='T'){
                countT++;
            }else{
                countF++;
            }
            if(countF>k&&countT>k){
                if(answerKey.charAt(left)=='T'){
                    countT--;
                }else{
                    countF--;
                }
                left++;
            }
            max=Math.max(max,right-left+1);
            right++;
        }
        return max;
    }
}
